package leetcode_题库;

import com.sun.org.apache.bcel.internal.generic.FSUB;

/**
 * Created by IntelliJ IDEA.
 *
 * @Author : Ding
 * @create 2022/8/17 14:46
 */
public class _53_最大子数组和 {
    public static void main(String[] args) {

//        int[] nums = new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int[] nums = new int[]{-2, -1, -3, -4, -1, -2, -1, -5, -4};

        System.err.println(funGreedy(nums));
    }

    public static int funGreedy(int[] nums) {
        int dynamicVal = 0;
        int ret = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            //先让其发生变化
            dynamicVal += nums[i];
            //此时，即使都是负数，也一定比MIN_VALUE大，所以赋值
            if (dynamicVal > ret) {
                ret = dynamicVal;
            }
            //这个时候再看是否小于0，重置
            if (dynamicVal < 0) {
                dynamicVal = 0;
            }
        }
        return ret;
    }

    public static int funDynamicPlan(int[] nums) {
        //动态规划：

        //记录第i个元素和第i-1个元素的关系（如果加了前面的比不加前面的数小了，就不加，否则就加）
        int pre = 0;
        //记录最大连续值
        int sumMax = nums[0];

        for (int item : nums) {
            //取item和item前面得值+item的较大值
            pre = Math.max(pre + item, item);
            //取pre和当前连续最大值的较大值
            sumMax = Math.max(pre, sumMax);
        }

        //输出
        return sumMax;
    }
}
